import ctypes
import os
from collections import defaultdict
from typing import Callable, List, Dict, Any

# 加载共享库
lib_path = "./libgraph_dfs.so"
if not os.path.exists(lib_path):
    # 编译 C++ 代码
    os.system("g++ -shared -fPIC -o libgraph_dfs.so graph_dfs.cpp -std=c++11")


class Graph:
    """Python 封装的图类，提供高级接口"""

    def __init__(self):
        self.lib = ctypes.CDLL(lib_path)

        # 定义函数原型
        self.lib.create_graph.restype = ctypes.c_void_p
        self.lib.create_graph.argtypes = []

        self.lib.add_node.argtypes = [ctypes.c_void_p, ctypes.c_int]
        self.lib.add_edge.argtypes = [ctypes.c_void_p, ctypes.c_int, ctypes.c_int]
        self.lib.get_node_count.argtypes = [ctypes.c_void_p]
        self.lib.get_node_count.restype = ctypes.c_int
        self.lib.get_edge_count.argtypes = [ctypes.c_void_p]
        self.lib.get_edge_count.restype = ctypes.c_int
        self.lib.destroy_graph.argtypes = [ctypes.c_void_p]

        # DFS 回调函数类型
        self.DFSCALLBACK = ctypes.CFUNCTYPE(
            None, ctypes.c_int, ctypes.c_int, ctypes.c_char_p
        )
        self.lib.dfs.argtypes = [ctypes.c_void_p, ctypes.c_int, self.DFSCALLBACK]

        self._graph = self.lib.create_graph()
        self._adj_list = defaultdict(list)

    def __del__(self):
        if hasattr(self, "_graph") and self._graph:
            self.lib.destroy_graph(self._graph)

    def add_node(self, node: int):
        """添加节点"""
        self.lib.add_node(self._graph, node)

    def add_edge(self, u: int, v: int):
        """添加边（无向图）"""
        self.lib.add_edge(self._graph, u, v)
        # 保持 Python 端的邻接表
        self._adj_list[u].append(v)
        self._adj_list[v].append(u)

    @property
    def node_count(self) -> int:
        """获取节点数量"""
        return self.lib.get_node_count(self._graph)

    @property
    def edge_count(self) -> int:
        """获取边数量"""
        return self.lib.get_edge_count(self._graph)

    def get_adjacency_list(self) -> Dict[int, List[int]]:
        """获取邻接表（Python 端）"""
        return dict(self._adj_list)

    def dfs(self, start: int, callback: Callable[[int, int, str], None] = None):
        """
        深度优先搜索
        :param start: 起始节点
        :param callback: 回调函数 (node, depth, status)
            status: 'VISIT', 'DISCOVER', 'COMPLETE'
        """
        # 如果没有回调，使用空函数
        if callback is None:
            callback = lambda *args: None

        # 定义回调包装器
        def c_callback(node, depth, status):
            callback(node, depth, status.decode("utf-8"))

        # 创建并传递回调函数
        c_callback_func = self.DFSCALLBACK(c_callback)
        self.lib.dfs(self._graph, start, c_callback_func)

    def visualize_dfs(self, start: int) -> str:
        """可视化 DFS 过程"""
        result = []
        indent = "  "

        def dfs_callback(node, depth, status):
            if status == "VISIT":
                result.append(f"{indent * depth}Visiting node {node}")
            elif status == "DISCOVER":
                result.append(f"{indent * depth}Discovering node {node}")
            elif status == "COMPLETE":
                result.append(f"{indent * depth}Completed node {node}")

        self.dfs(start, dfs_callback)
        return "\n".join(result)


# 测试代码
if __name__ == "__main__":
    print("=== 图 DFS 测试 (ctypes) ===")

    # 创建图
    g = Graph()
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 4)
    g.add_edge(2, 5)
    g.add_edge(3, 6)
    g.add_edge(5, 7)
    g.add_edge(6, 8)

    print(f"图信息: {g.node_count} 个节点, {g.edge_count} 条边")
    print("邻接表:", g.get_adjacency_list())

    # 测试 DFS
    print("\nDFS 遍历 (从节点 1):")

    def dfs_callback(node, depth, status):
        status_symbol = {"VISIT": "→", "DISCOVER": "+", "COMPLETE": "✓"}.get(
            status, "?"
        )
        print(f"{'  ' * depth}{status_symbol} 节点 {node} ({status})")

    g.dfs(1, dfs_callback)

    # 可视化 DFS
    print("\nDFS 可视化:")
    print(g.visualize_dfs(1))
